package a06_栈与队列;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

/**
 * <p>
 * a07_滑动窗口最大值复习4
 * </p>
 *
 * @author flyduck
 * @since 2025/5/19
 */
public class a07_滑动窗口最大值复习4 {

    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        System.out.println(list.peekFirst());//1
        System.out.println(list.peekLast());//3

        a07_滑动窗口最大值复习4 test = new a07_滑动窗口最大值复习4();
        System.out.println(Arrays.toString(test.maxSlidingWindow(new int[]{1,3,-1,-3,5,3,6,7},3)));
    }

    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] result = new int[nums.length-k+1];
        int resultIdx = 0;

        MyDeque5 myDeque5 = new MyDeque5();
        for (int i = 0; i < k; i++) {
            myDeque5.push(nums[i]);
        }
        result[resultIdx] = myDeque5.getMax();
        resultIdx++;

        for (int i = k; i < nums.length; i++) {
            myDeque5.pop(nums[i-k]);
            myDeque5.push(nums[i]);
            result[resultIdx] = myDeque5.getMax();
            resultIdx++;
        }
        return result;
    }
}

//1,3,-1,-3,5,3,6,7
class MyDeque5{

    private LinkedList<Integer> list = new LinkedList<>();

    public void push(int value){
        if(list.isEmpty()){
            list.add(value);
        }else {
            if(list.peekLast() >= value){
                list.add(value);
            }else {
                while (!list.isEmpty() && list.peekLast() < value){
                    list.pollLast();
                }
                list.add(value);
            }
        }

    }

    public void pop(int value){
        if(list.peekFirst().equals(value)){
            list.pollFirst();
        }
    }

    public int getMax(){
        return list.peekFirst();
    }
}
